home *** CD-ROM | disk | FTP | other *** search
Wrap
Text File | 1996-04-25 | 15.5 KB | 397 lines | [ TEXT/CWIE]
//================================================================================ // Greg Anderson // db+ // // Cursor to an database record record // 16 May 1994 //================================================================================ #pragma once #ifndef __ABSTRACTDBRECORD__ #define __ABSTRACTDBRECORD__ // // Abstract cursor is the base class for TDBRecord // #include "AbstractRecord.h" // // For CompareEnumeration // #include "AbstractData.h" // // For REQUIREVALIDPOINTER // #include "Exceptions.h" // // There are some fields common to both object records and property // records. Why have two abstract classes rather than define these // methods in TAbstractRecord? The only reason is to keep all // knowledge of the type of information in the records out of the // low level interface and up in the middle level interface. // // Fields: // // Flags // Parent sibling // Left sibling // Right sibling // // Next four longwords vary based on the type of the record // // Identifier of data record or parent element of object record // Data or index of record at top of element tree // Data or index of record at top of property tree // Data or index of name property // // Flag bits: // // DB Records: // // b31-b30: AVL balance factor (left high, equal, right high) // b29: Set = record is at top of tree, clear = record is a sub-node // // Object records: // // b28: Clear = object record (set = some other kind of record) // b27-b0: Node number // // Data records: // // b28: Set // b27: Clear = data record (set = some other kind of record) // b26-b16: Unused // b15-b8: Encoded data type // b7-b0: Length of data (or zero if not applicable) // // So far, b28 & b27 set is an undefined combination unless ALL bits in // the flag word are set (which indicates a free DB record) // // Important: The first two bits of the flags longword must be nonzero, // as 00 identifies a block data record (see GroupControlObject.h) // enum { kRecordFlagsWord = 0, kParentSiblingWord, kLeftSiblingWord, kRightSiblingWord, kIDOrParentElementIndex, kNamePropertyWord, kTopPropertyWord, kTopChildWord }; // // Flag bits: // enum { kBalanceFactorBits = 0xC0000000, kLeftSideHigher = 0x80000000, kSubtreesBalanced = 0xC0000000, kRightSideHigher = 0x40000000, kTopOfTreeBit = 0x20000000, kObjectRecordDefinitionBit = 0x10000000, // CLEAR for object records kObjectRecordReservedRecordBits = 0x0FFFFFFF, kDataRecordDefinitionBit = 0x08000000, // CLEAR for data records kDataRecordReservedRecordBits = 0x07FFFFFF }; // // Enumerations for initial values for flag bits // // Note that in the initial object record flags, kObjectRecordDefinitionBit is CLEAR // and in the initial data record flags, kDataRecordDefinitionBit is CLEAR // enum { kInitialObjectRecordFlags = (kSubtreesBalanced | kTopOfTreeBit), kInitialDataRecordFlags = (kSubtreesBalanced | kObjectRecordDefinitionBit | kTopOfTreeBit) }; enum ChildIdentifier { kNodeIsLeftChild, kNodeIsRightChild, kNodeIsTopOfElementTree, kNodeIsTopOfPropertyTree, kNodeIsNotAChild }; class TAbstractDBComparisonObject; //================================================================================ // Class TDBRecord //================================================================================ class TDBRecord : public TAbstractRecord { // // ----- Fields -------------------------------------------------------------- // protected: // // ----- Methods ------------------------------------------------------------- // public: TDBRecord(TDatabaseDocument* doc, long recordIndex) : TAbstractRecord(doc, recordIndex) {}; virtual ~TDBRecord(); //:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: // Methods of TAbstractRecord: //:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: public: virtual void FreeOwnedData(TTransaction* t); virtual void FreeThisRecord(TTransaction* t); protected: virtual const TDBRecord* AbstractDBRecord() const { return this; }; //:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: // Public interface: const methods //:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: public: // // Basic navagation: // virtual AConst<TDBRecord> TreeOwner(TTransaction* t) const; AConst<TDBRecord> FirstItemInTree(TTransaction* t) const; AConst<TDBRecord> LastItemInTree(TTransaction* t) const; AConst<TDBRecord> NextItemInTree(TTransaction* t) const; AConst<TDBRecord> PreviousItemInTree(TTransaction* t) const; AConst<TDBRecord> FindItemInTree(TTransaction* t, TAbstractDBComparisonObject* doCompare) const; // // Subtree searching: Probably not generally useful, but slightly faster if // you know you already have the top item in the tree // AConst<TDBRecord> FirstItemInSubTree(TTransaction* t) const; AConst<TDBRecord> LastItemInSubTree(TTransaction* t) const; AConst<TDBRecord> FindItemInSubTree(TTransaction* t, TAbstractDBComparisonObject* doCompare) const; // // Navigation methods most people won't need to use // AConst<TDBRecord> TopOfTree(TTransaction* t) const; AConst<TDBRecord> LeftSibling(TTransaction* t) const { return this->GetDBRecordCursor(this->LeftSiblingIndex(t)); } AConst<TDBRecord> RightSibling(TTransaction* t) const { return this->GetDBRecordCursor(this->RightSiblingIndex(t)); } AConst<TDBRecord> ParentSibling(TTransaction* t) const { return this->RecordIsAtTopOfTree(t) ? AConst<TDBRecord>(nil) : LiteralParentSibling(t); } // // Tests to do before navagation, if you'd like to peek before going there: // Boolean RecordIsInATree(TTransaction* t) const { return this->ParentSiblingIndex(t) != kNilIndex; } Boolean RecordIsAtTopOfTree(TTransaction* t) const { return (this->RecordFlags(t) & kTopOfTreeBit) != 0; } Boolean HasLeftSibling(TTransaction* t) const { return this->LeftSiblingIndex(t) != kNilIndex; } Boolean HasRightSibling(TTransaction* t) const { return this->RightSiblingIndex(t) != kNilIndex; } long NumberOfChildSiblings(TTransaction* t) const; // // Usually you should use the more specific routines for accessing // the elements or properties of a record; see TDBElement // AConst<TDBRecord> TopElementRecord(TTransaction* t) const { return this->GetDBRecordCursor(this->TopChildIndex(t)); }; AConst<TDBRecord> TopPropertyRecord(TTransaction* t) const { return this->GetDBRecordCursor(this->TopPropertyIndex(t)); }; // // Now we're getting so obscure, this should almost be in the protected interface. // Avoid calling these routines. // AConst<TDBRecord> LiteralParentSibling(TTransaction* t) const { return this->GetDBRecordCursor(this->ParentSiblingIndex(t)); }; AConst<TDBRecord> GoUpUntil(TTransaction* t, ChildIdentifier fromDirection) const; virtual ChildIdentifier IdentifyChild(TTransaction* t, AConst<TDBRecord>) const; // // CompareSortKeys should compare the keys of the two nodes and return // whether the second is larger, smaller or equal than the first. // // CompareTreeOrder does the same thing as CompareSortKeys, but it is // _never_ allowed to return equal; one node must always be larger than // the other. // virtual CompareEnumeration CompareSortKeys(TTransaction* t, AConst<TDBRecord> secondObject) const = 0; virtual CompareEnumeration CompareTreeOrder(TTransaction* t, AConst<TDBRecord> secondObject) const; static CompareEnumeration DetermineCompareEnumeration(long key1, long key2) { return key2 < key1 ? kSecondObjectComesBefore : (key2 > key1 ? kSecondObjectComesAfter : kObjectKeysEqual ); }; // // Do debugging tests on this node // long DeepestSubtree(TTransaction* t) const; virtual void Verify(TTransaction* t, Boolean verifyDeep = false) const; //:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: // Public interface: non-const methods //:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: public: Boolean Insert(TTransaction* t, AnUpdate<TDBRecord>); virtual void RemoveFromTree(TTransaction* t); // // The method "ResortThisRecord" should be called whenever the sort key // for this record changes; doing that removes and re-inserts this record // in the tree it is currently contained in. This is done automatically // by TDBProperty, so this method should probably be protected. // void ResortThisRecord(TTransaction* t); // // Usually, only the database document will call this method; // use TDatabaseDocument::NewDBProperty(TTransaction*) and // TDatabaseDocument::NewDBElement(TTransaction*) to get new // database records to work with // virtual void InitializeNewRecord(TTransaction* t); // // Usually, only a property record will call this method // virtual void PropertyValueChanged(TTransaction* t, AConst<TDBProperty> propertyThatChanged); //:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: // Protected interface: const methods //:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: protected: long RecordFlags(TTransaction* t) const { return this->GetRecordData(t, kRecordFlagsWord); }; long ParentSiblingIndex(TTransaction* t) const { return this->GetRecordData(t, kParentSiblingWord); }; long LeftSiblingIndex(TTransaction* t) const { return this->GetRecordData(t, kLeftSiblingWord); }; long RightSiblingIndex(TTransaction* t) const { return this->GetRecordData(t, kRightSiblingWord); }; // // Usually, only object records own children and property trees. // However, there are some types of data records that may also own // trees; when they do, their pointer to the top record of the tree // is always in the same index as the same field in an object // record. Therefore, we abstract these field as if it were a // member of every DB cursor, even though they might not exist in // some records. // // RequireRecordCanHaveElements / RequireRecordCanHaveProperties // will fail if the record cannot contain elements/properties, // or do nothing if elements/properties are okay // virtual Boolean RecordCanHaveElements(TTransaction* t) const; virtual Boolean RecordCanHaveProperties(TTransaction* t) const; void RequireRecordCanHaveElements(TTransaction* t) const; void RequireRecordCanHaveProperties(TTransaction* t) const; long TopChildIndex(TTransaction* t) const { this->RequireRecordCanHaveElements(t); return this->GetRecordData(t, kTopChildWord); }; long TopPropertyIndex(TTransaction* t) const { this->RequireRecordCanHaveProperties(t); return this->GetRecordData(t, kTopPropertyWord); }; long BalanceFactor(TTransaction* t) const { return this->RecordFlags(t) & kBalanceFactorBits; }; virtual long FreeListToUse(TTransaction*) { return 0; } // we have a constant for this "0" (kFreeRecordListIndex), but right now it's in RecordGroupControlObject.h //:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: // Protected interface: non-const methods //:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: protected: void SetRecordFlags(TTransaction* t, long newValue) { this->ChangeRecordData(t, kRecordFlagsWord, newValue); }; void SetParentSiblingIndex(TTransaction* t, long newValue) { this->ChangeRecordData(t, kParentSiblingWord, newValue); }; void SetLeftSiblingIndex(TTransaction* t, long newValue) { this->ChangeRecordData(t, kLeftSiblingWord, newValue); }; void SetRightSiblingIndex(TTransaction* t, long newValue) { this->ChangeRecordData(t, kRightSiblingWord, newValue); }; void SetRecordIsAtTopOfTree(TTransaction* t, Boolean atTop) { this->SetRecordFlags(t, (this->RecordFlags(t) & ~kTopOfTreeBit) | (atTop ? kTopOfTreeBit : 0)); }; void SetBalanceFactor(TTransaction* t, long newFactor) { this->SetRecordFlags(t, (this->RecordFlags(t) & ~kBalanceFactorBits) | (newFactor & kBalanceFactorBits)); }; void SetTopChildIndex(TTransaction* t, long newValue) { this->RequireRecordCanHaveElements(t); this->ChangeRecordData(t, kTopChildWord, newValue); }; void SetTopPropertyIndex(TTransaction* t, long newValue) { this->RequireRecordCanHaveProperties(t); this->ChangeRecordData(t, kTopPropertyWord, newValue); }; void SetLeftSibling(TTransaction* t, AConst<TDBRecord> cursor) { this->SetLeftSiblingIndex(t, cursor.Exists() ? cursor->RecordIndex() : kNilIndex); }; void SetRightSibling(TTransaction* t, AConst<TDBRecord> cursor) { this->SetRightSiblingIndex(t, cursor.Exists() ? cursor->RecordIndex() : kNilIndex); }; void SetParentSibling(TTransaction* t, AConst<TDBRecord> cursor) { this->SetParentSiblingIndex(t, cursor.Exists() ? cursor->RecordIndex() : kNilIndex); }; void SetElements(TTransaction* t, AConst<TDBRecord> cursor) { this->SetTopChildIndex(t, cursor.Exists() ? cursor->RecordIndex() : kNilIndex); }; void SetProperties(TTransaction* t, AConst<TDBRecord> cursor) { this->SetTopPropertyIndex(t, cursor.Exists() ? cursor->RecordIndex() : kNilIndex); }; void SetChildLinkOfNewParent(TTransaction* t, AConst<TDBRecord> newChild, ChildIdentifier whichChild); ChildIdentifier SetParentsLinkToThisNodeTo(TTransaction* t, AConst<TDBRecord> newChild); void SwapTreePositions(TTransaction* t, AnUpdate<TDBRecord> swapWith); void FreeEntireTree(TTransaction* t); //:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: // Private methods: //:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: private: void RightBalance(TTransaction* t); void LeftBalance(TTransaction* t); void RotateLeft(TTransaction* t); void RotateRight(TTransaction* t); void DoubleRotateRightSide(TTransaction* t); void DoubleRotateLeftSide(TTransaction* t); }; //================================================================================ // Class TAbstractDBComparisonObject //================================================================================ class TAbstractDBComparisonObject { public: virtual CompareEnumeration TestObject(TTransaction*, AConst<TDBRecord>) = 0; }; // // Iteration direction // enum { kIterateForward = 0, kIterateBackward }; //================================================================================ // Class TAbstractRecordIterator // // Give the constructor a AConst<TDBRecord>, and the iterator will iterate over // all of the siblings of the record + the record itself. So, to iterate over // the properties of a record: // // properties = cursor->Properties(); // for(TAbstractRecordIterator iter(properties); iter.More(); iter.Next()) // ... do stuff //================================================================================ class TAbstractRecordIterator { private: AConst<TDBRecord> fCursor; AConst<TDBRecord> fCurrent; Boolean fDirection; Boolean fHaveRemovedCurrent; TTransaction* fTransaction; public: TAbstractRecordIterator(TTransaction* t, AConst<TDBRecord> cursor, Boolean = kIterateForward); virtual ~TAbstractRecordIterator(); Boolean IterateForward() const { return fDirection == kIterateForward; } void Reset(Boolean direction = kIterateForward); Boolean More() const { return fCurrent.Exists(); } void Next(); void RemoveCurrent(); AConst<TDBRecord> Current() { return fCurrent; } TTransaction* Transaction() { return fTransaction; } }; #endif